package com.gemini.main.sort;

public class BSearch {

    /**
     * 二分查找第一个等于value的元素
     *
     * @param a     数组
     * @param value 要查找的值
     * @return
     */
    public static int bsearch(int[] a, int value) {
        int low = 0, n = a.length, high = a.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value)// 相等的情况下继续往前查找
                high = mid - 1;
            else
                low = mid + 1;
        }

        if (low < n && a[low] == value) return low;
        return -1;
    }

    public static int bsearch1(int[] a, int value) {
        int low = 0, high = a.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {// 相等的情况下继续往前查找
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                // 相等继续往前查找，如果是第一个或者前一个不相等直接返回
                if (mid == 0 || a[mid - 1] != value) return mid;
                else high = mid - 1;
            }

        }
        return -1;
    }


    public static void main(String[] args) {
        int[] a = {2, 4, 6, 8};
        int value = 2;
        bsearch(a, value);
    }
}
